DP N

Attach adjacent objects

Cost varies depending on the order of attachment.

Cost minimization issues

DP with the domain as the domain of definition

Same as [DP L

DP as the value of the lowest cost to attach the area when the area is specified.

code:python

def solve(N, XS):

@lru_cache(maxsize=None)

def sub(L, R):

if L == R:

return 0

ret = INF

for x in range(L, R):

v = sub(L, x) + sub(x + 1, R)

if v < ret:

ret = v

return sub(0, N - 1)

Cython

code:python

cdef sub(long L, long R):

cdef long long ret

if L == R:

return 0

if ret != 0:

return ret

ret = INF

for x in range(L, R):

v = sub(L, x) + sub(x + 1, R)

if v < ret:

ret = v

return ret

cdef solve(N, XS):

cdef long i

cdef long long v

v = 0

for i in range(N):

return sub(0, N - 1)

---